package _09_高频题;

/**
 * https://leetcode-cn.com/problems/powx-n/
 * @Author: haogege
 * @Date: 2021/9/3
 */
public class _50_pow {

    // 求n次幂的模运算, 如果对于x，y都很大的话，算出的结果将会溢出，所以可以分别取模
    // (x * y) % z == ((x % z) * (y % z)) % z
    public static int powMod1(int x, int y, int z) {
        // 小数模运算一般不在
        if (y < 0 || z == 0) return 0;
        int res = 1 % z;
        x = x % z;
        while (y > 0) {
            if ((y & 1) == 1) {
                res = (res * x) % z;
            }
            x = (x * x) % z;
            y >>= 1;
        }
        return res;
    }

    // 递归, 函数作用，返回取模后的结果
    public static int powMod(int x, int y, int z) {
        if (y < 0 || z == 0) return 0;
        if (y == 0) return 1 % z;
        // 递归运算
        int half = powMod(x, y >> 1, z);
        // 判断指数是奇还是偶
        half *= half;
        if ((y & 1) == 1) {
            // 奇数
            return (half * (x % z)) % z;
        } else {
            // 偶数
            return half  % z;
        }
    }

    // 非递归运算, 快速幂运算
    public double myPow(double x, int n) {
        // 防止溢出
        long y = n < 0? -((long) n): n;
        // 逐渐右移
        double res = 1.0;
        while (y > 0) {
            if ((y & 1) == 1) {
                // 奇数
                res *= x;
            }
            x *= x;
            y >>= 1;
        }
        return n < 0? 1 / res: res;
    }


    // 折半查找, 对于负数，右移运算奇数可以认为是先上取整，所以奇数情况下，直接乘以x即可
    public double myPow1(double x, int n) {
        if (n == 0) return 1.0;
        if (n == -1) return 1 / x;
        double half = myPow1(x, n >> 1);
        half *= half;
        return (n & 1) == 1? half * x: half;
    }
    public static void main(String[] args) {
        System.out.println(powMod1(-123, 455, 789));
        System.out.println(powMod(-123, 455, 789));
    }

    
}
